package 算法.动态规划;

public class JZ63买卖股票的最好时机1 {
    //动态规划
    public int maxProfit (int[] prices) {
        // write code here
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[prices.length][2];
        //第一天不持股，总收益为0
        dp[0][0] = 0;
        //第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0];
        //遍历后续每天，状态转移
        for(int i = 1; i < prices.length; i++){
            //卖出必须在买入之前
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[prices.length - 1][0];
    }

    //贪心
    public int maxProfit1 (int[] prices) {
        //维护最大收益
        int res = 0;
        //排除特殊情况
        if(prices.length == 0)
            return res;
        //维护最低股票价格
        int Min = prices[0];
        //遍历后续股票价格
        for(int i = 1; i < prices.length; i++){
            //如果当日价格更低则更新最低价格
            Min = Math.min(Min, prices[i]);
            //维护最大值
            res = Math.max(res, prices[i] - Min);
        }
        return  res;
    }
}
